package tree

/*

树（Tree）：由一个root节点 + 其任意多个子节点
树（Tree）：由 𝑛≥0个节点与节点之间的关系组成的有限集合,N=0 为空数
*/
/*
==== 树的节点
「树的节点」 由一个数据元素和若干个指向其子树的树的分支组成。而节点所含有的子树个数称为 「节点的度」（子节点个数）。
度为0 的节点称为 「叶子节点」 或者 「终端节点
度不为0 的节点称为 「分支节点」 或者 「非终端节点」。
树中各节点的最大度数称为 「树的度」。


节点的层次    :从根节点开始定义，根为第1 层，根的子节点为第2层
树的深度（高度） :所有节点中最大的层数。
堂兄弟节点    :父节点在同一层的节点互为堂兄弟
路径       :树中两个节点之间所经过的节点序列
路径长度     :两个节点之间路径上经过的边数
节点的祖先    :从该节点到根节点所经过的所有节点，被称为该节点的祖先
节点的子孙    :节点的子树中所有节点被称为该节点的子孙
*/
/*
==== 树的分类

根据节点的子树是否可以互换位置，我们可以将树分为两种类型：「有序树」 和 「无序树」。

如果将树中节点的各个子树看做是从左到右是依次有序的（即不能互换），则称该树为 「有序树
*/

/*
二叉树简介
2.1 二叉树的定义
二叉树（Binary Tree）：树中各个节点的度不大于2 个的有序树，称为二叉树。
通常树中的分支节点被称为 「左子树」 或 「右子树」。
	二叉树的分支具有左右次序，不能随意互换位置。


二叉树也可以使用递归方式来定义，即二叉树满足以下两个要求之一
空树：二叉树是一棵空树
非空树：二叉树是由一个根节点和两棵互不相交的子树 T1 T2，分别称为根节点的左子树、右子树组成的非空树；并且  本身都是二叉树

二叉树在逻辑上可以分为5 种基本形态
空 根 左子 右子 左右都有


===特殊的二叉树


满二叉树:除了叶子节点之外，每个节点都有左右两个子节点 所有叶子结点必须在同一层上
	叶子节点只出现在最下面一层
	非叶子节点的度一定为2
　　1) 一颗树深度为h，最大层数为k，深度与最大层数相同，k=h;
　　2) 叶子数为2h;
　　3) 第k层的结点数是：2k-1;
　　4) 总结点数是：2k-1，且总节点数一定是奇数。



完全二叉树
如果叶子节点只能出现在最下面两层，
并且最下层的叶子节点都依次排列在该层最左边的位置上，
具有这种特点的二叉树称为完全二叉树。
完全二叉树满足以下特点：

	叶子节点只能出现在最下面两层。
	最下层的叶子节点一定集中在该层最左边的位置上。
	倒数第二层如果有叶子节点，则该层的叶子节点一定集中在右边的位置上。
	如果节点的度为	1，则该节点只偶遇左孩子节点，即不存在只有右子树的情况。
	同等节点数的二叉树中，完全二叉树的深度最小。


二叉搜索树
二叉查找树、有序二叉树或者排序二叉树。是指一棵空树或者具有下列性质的二叉树
	如果任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值。
	如果任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值。
	任意节点的左子树、右子树均为二叉搜索树

平衡二叉搜索树
一种结构平衡的二叉搜索树。即叶节点高度差的绝对值不超过 1，
并且左右两个子树都是一棵平衡二叉搜索树。
平衡二叉树可以在O(log n) 内完成插入、查找和删除操作

=====二叉树的存储结构

二叉树的存储结构分为两种：「顺序存储结构」和「链式存储结构」

顺序存储结构
	二叉树的顺序存储结构使用一维数组来存储二叉树中的节点，节点存储位置则采用完全二叉树的节点层次编号，按照层次从上至下，
	每一层从左至右的顺序依次存放二叉树的数据元素。在进行顺序存储时，如果对应的二叉树节点不存在，则设置为「空节点


	如果某二叉树节点（非叶子节点）的下标为 i，那么其左孩子节点下标为 2*i +1  右孩子节点下标为 2*i+2
	如果某二叉树节点（非叶子节点）的下标为 i，那么其root节点下标为 (i-1)//2  //表示整除


	对于完全二叉树（尤其是满二叉树）来说，采用顺序存储结构比较合适，它能充分利用存储空间
	而对于一般二叉树，如果需要设置很多的「空节点」，则采用顺序存储结构就会浪费很多存储空间

链式存储结构
二叉树采用链式存储结构 left value right 左右两个孩子节点 与值

*/

/*
堆(Heap)是计算机科学中一类特殊的数据结构的统称。

堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆满足下列性质：

堆中某个节点的值总是不大于或不小于其父节点的值。
堆总是一棵完全二叉树。
*/
